Outline of discrete mathematics

The following outline is presented as an overview of and topical guide to discrete mathematics:

Discrete mathematics – study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic^[1] – do not vary smoothly in this way, but have distinct, separated values.^[2] Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus and analysis.

Included below are many of the standard terms used routinely in university-level courses and in research papers. This is not, however, intended as a complete list of mathematical terms; just a selection of typical terms of art that may be encountered.

Contents 1 Subjects in discrete mathematics 2 Discrete mathematical disciplines 3 Concepts in discrete mathematics 3.1 Sets 3.2 Functions 3.3 Operations 3.4 Arithmetic 3.5 Elementary algebra 3.6 Mathematical relations 3.7 Mathematical phraseology 3.8 Combinatorics 3.9 Probability 3.10 Propositional logic 4 Discrete mathematicians 5 See also 6 References 7 External links

Subjects in discrete mathematics

• Logic – a study of reasoning
• Set theory – a study of collections of elements
• Number theory –
• Combinatorics – a study of counting
• Graph theory –
• Digital geometry and digital topology
• Algorithmics – a study of methods of calculation
• Information theory –
• Computability and complexity theories – dealing with theoretical and practical limitations of algorithms
• Elementary probability theory and Markov chains
• Linear algebra – a study of related linear equations
• Functions –
• Partially ordered set –
• Probability –
• Proofs –
• Counting –
• Relation –

Discrete mathematical disciplines

For further reading in discrete mathematics, beyond a basic level, see these pages. Many of these disciplines are closely related to computer science.

• Automata theory –
• Combinatorics –
• Combinatorial geometry –
• Computational geometry –
• Digital geometry –
• Discrete geometry –
• Graph theory –
• Mathematical logic –
• Combinatorial optimization –
• Set theory –
• Combinatorial topology –
• Number theory –
• Information theory –
• Game theory –

Concepts in discrete mathematics

Sets

• Set (mathematics) –
  • Element (mathematics) –
  • Venn diagram –
  • Empty set –
  • Subset –
  • Union (set theory) –
    • Disjoint union –
  • Intersection (set theory) –
    • Disjoint sets –
  • Complement (set theory) –
  • Symmetric difference –
• Ordered pair –
• Cartesian product –
• Power set –
• Simple theorems in the algebra of sets –
• Naive set theory –
• Multiset –

Functions

• Function –
• Domain of a function –
• Codomain –
• Range of a function –
• Image (mathematics) –
• Injective function –
• Surjection –
• Bijection –
• Function composition –
• Partial function –
• Multivalued function –
• Binary function –
• Floor function –
• Sign function –
• Inclusion map –
• Pigeonhole principle –
• Relation composition –
• Permutations –
• Symmetry –

Operations

Binary operator –

• Associativity –
• Commutativity –
• Distributivity

Arithmetic

Decimal –

• Binary numeral system –
• Divisor –
• Division by zero –
• Indeterminate form –
• Empty product –
• Euclidean algorithm –
• Fundamental theorem of arithmetic –
• Modular arithmetic –
• Successor function

Elementary algebra

Left-hand side and right-hand side of an equation –

• Linear equation –
• Quadratic equation –
• Solution point –
• Arithmetic progression –
• Recurrence relation –
• Finite difference –
• Difference operator –
• Groups –
• Group isomorphism –
• Subgroups –
• Fermat's little theorem –
• Cryptography –
• Faulhaber's formula –

Mathematical relations

• Binary relation –
• Mathematical relation –
• Reflexive relation –
• Reflexive property of equality –
• Symmetric relation –
• Symmetric property of equality –
• Antisymmetric relation –
• Transitivity (mathematics) –
  • Transitive closure –
  • Transitive property of equality –
• Equivalence and identity
  • Equivalence relation –
  • Equivalence class –
  • Equality (mathematics) –
    • Inequation –
    • Inequality (mathematics) –
  • Similarity (geometry) –
  • Congruence (geometry) –
  • Equation –
  • Identity (mathematics) –
    • Identity element –
    • Identity function –
  • Substitution property of equality –
  • Graphing equivalence –
  • Extensionality –
  • Uniqueness quantification –

Mathematical phraseology

If and only if –

• Necessary and sufficient (Sufficient condition) –
• Distinct –
• Difference –
• Absolute value –
• Up to –
• Modular arithmetic –
• Characterization (mathematics) –
• Normal form –
• Canonical form –
• Without loss of generality –
• Vacuous truth –
• Contradiction, Reductio ad absurdum –
• Counterexample –
• Sufficiently large –
• Pons asinorum –
• Table of mathematical symbols –
• Contrapositive –
• Mathematical induction –

Combinatorics

• Permutations and combinations –
• Permutation –
• Combination –
• Factorial –
  • Empty product –
• Pascal's triangle –
• Combinatorial proof –
  • Bijective proof –
  • Double counting (proof technique) –

Probability

• Average –
• Expected value –
• Discrete random variable –
• Sample space –
• Event –
• Conditional Probability –
• Independence –
• Random variables –

Propositional logic

Logical operator –

• Truth table –
• De Morgan's laws –
• Open sentence –
• List of topics in logic –

Discrete mathematicians

Paul Erdős –

• Ronald Graham –

See also

References

External links

• Archives
• Jonathan Arbib & John Dwyer, Discrete Mathematics for Cryptography, 1st Edition ISBN 978-1907934018.
• John Dwyer & Suzy Jagger, Discrete Mathematics for Business & Computing, 1st Edition 2010 ISBN 978-1907934001.

Logic   Overview Academic areas Argumentation theory Axiology Critical thinking Computability theory Formal semantics History of logic Informal logic Logic in computer science Mathematical logic Mathematics Metalogic Metamathematics Model theory Philosophical logic Philosophy Philosophy of logic Philosophy of mathematics Proof theory Set theory Foundational concepts Abduction Analytic truth Antinomy A priori Deduction Definition Description Entailment Induction Inference Logical consequence Logical form Logical implication Logical truth Name Necessity Meaning Paradox Possible world Presupposition Probability Reason Reasoning Reference Semantics Statement Strict implication Substitution Syntax Truth Truth value Validity   Philosophical logic Critical thinking and Informal logic Analysis Ambiguity Argument Belief Bias Credibility Evidence Explanation Explanatory power Fact Fallacy Inquiry Opinion Parsimony Premise Propaganda Prudence Reasoning Relevance Rhetoric Rigor Vagueness Theories of deduction Constructivism Dialetheism Fictionalism Finitism Formalism Intuitionism Logical atomism Logicism Nominalism Platonic realism Pragmatism Realism   Metalogic and metamathematics Cantor's theorem Church's theorem Church's thesis Consistency Effective method Foundations of mathematics Gödel's completeness theorem Gödel's incompleteness theorems Soundness Completeness Decidability Interpretation Löwenheim–Skolem theorem Metatheorem Satisfiability Independence Type–token distinction Use–mention distinction   Mathematical logic General Formal language Formation rule Formal system Deductive system Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Natural deduction Rule of inference Relation Theorem Logical consequence Axiomatic system Type theory Symbol Syntax Theory Traditional logic Proposition Inference Argument Validity Cogency Syllogism Square of opposition Venn diagram Propositional calculus and Boolean logic Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables Predicate First-order Quantifiers Predicate Second-order Monadic predicate calculus Set theory Set Empty set Enumeration Extensionality Finite set Function Subset Power set Countable set Recursive set Domain Range Ordered pair Uncountable set Model theory Model Interpretation Non-standard model Finite model theory Truth value Validity Proof theory Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax Computability theory Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function   Non-classical logic Modal logic Alethic Axiologic Deontic Doxastic Epistemic Temporal Intuitionism Intuitionistic logic Constructive analysis Heyting arithmetic Intuitionistic type theory Constructive set theory Fuzzy logic Degree of truth Fuzzy rule Fuzzy set Fuzzy finite element Fuzzy set operations Substructural logic Structural rule Relevance logic Linear logic Paraconsistent logic Dialetheism Description logic Ontology Ontology language   Logicians Anderson Aristotle Averroes Avicenna Bain Barwise Bernays Boole Boolos Cantor Carnap Church Chrysippus Curry De Morgan Frege Geach Gentzen Gödel Hilbert Kleene Kripke Leibniz Löwenheim Peano Peirce Putnam Quine Russell Schröder Scotus Skolem Smullyan Tarski Turing Whitehead William of Ockham Wittgenstein Zermelo   Lists Topics Outline of logic Index of logic articles Mathematical logic Boolean algebra Set theory Other Logicians Rules of inference Paradoxes Fallacies Logic symbols Portal Category Outline WikiProject Talk changes

Outlines General reference Culture and the arts Geography and places Health and fitness History and events Mathematics and logic Natural and physical sciences People and self Philosophy and thinking Religion and belief systems Society and social sciences Technology and applied sciences